\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{arrows,snakes,backgrounds}
\usetikzlibrary{positioning, shapes.geometric}
\title{作业六: 图的模板类设计}
\author{冯皓 \\ 数学与应用数学（强基计划） 3210100135}
\begin{document}
\maketitle
\section{设计思路与数据结构关系}
本次设计的基础是graph的边，用含起点，终点和权重的结构来定义边，其次我分别用数组和链表构建邻接矩阵和邻接表，根据用户的选择来选择储存形势，若不选择，则默认邻接表（这样可以减小储存空间）。为了体现交互功能，我们需要用户用通过添加边的方式来构建图，由此设计了addedge函数，具体数据结构的关系由下图表示：
\par
\par
\begin{tikzpicture}[node distance = 1.5cm][h]
\centering
\tikzstyle{startstop} = [rectangle, rounded corners, minimum width=3cm, minimum height=1cm,text centered, draw=black];
\tikzstyle{startstop2} = [rectangle, rounded corners, minimum width=2cm, minimum height=1cm,text centered, draw=black];
\tikzstyle{decision} = [diamond, draw, text width=5.5em, text badly centered, inner sep=0pt];
\tikzstyle{process} = [rectangle, minimum width=3cm, minimum height=1cm, text centered, draw=black];
\tikzstyle{arrow} = [thick,->,>=stealth];
\node (start)[startstop]{边的结构};
\node (decP) [startstop2, left of=start, xshift=-0.5cm,yshift=-1.5cm]{链表};
\node (dec2) [startstop2,right of=start,xshift=0.5cm, yshift=-1.5cm]{二维数组};
\node (result1)[startstop,left of=start, xshift=-2cm, yshift=-3cm]{邻接表};
\node (result4)[startstop,right of=start, xshift=2cm, yshift=-3cm]{邻接矩阵};
\node (result2) [startstop,below of=start,yshift=-3.5cm]{graph};
\draw [arrow] (start) -| node[near start, above] {}(result1);
\draw [arrow] (start) -| node[near start, above] {}(result4);
\draw [arrow] (decP) --(result1);
\draw [arrow] (dec2) --(result4);
\draw [arrow] (result1) --(result2);
\draw [arrow] (result4) --(result2);
\end{tikzpicture}
\par 其次我设计了成员函数listVertexes和listEdges，方便起见，默认节点的名称为整数，但对边的权重不提任何要求。由于我在含参构造中希望用户将节点的名称以数组的形式输入，对于节点的输出仅需将输入的内容输出即可。而listEdges的设计，我利用了edge这个结构来储存，输出。
\section{测试算例}
输入一个4个节点的图，并加入四条边edge(1,2,1)，edge(1,3,2)，edge(3,2,3)，edge(4,1,4)，分别用邻接表和邻接矩阵进行储存，然后再把权重变为一，测试无向图的情况，最后输出结果如下（为了节省空间，一部分换行用空格代替）：
\begin{verbatim}
邻接表：(1,2,1) (1,3,2) (3,2,3) (4,1,4) 1 2 3 4 
邻接矩阵：(1,2,1) (1,3,2)(3,2,3) (4,1,4) 1 2 3 4 
无向图：(1,2,1) (1,3,1) (1,4,1) (2,1,1) (2,3,1) (3,1,1) (3,2,1) (4,1,1)
 1 2 3 4 
\end{verbatim}
\par 可见最终的结果符合预期
\end{document}